class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), 
            [](int a, int b) {return abs(a) < abs(b);}
            );
        for (int i = nums.size() - 1; i >= 0 && k; i--) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k && k % 2 != 0) nums[0] = -nums[0];
        int sum = 0;
        for (auto x : nums) sum += x;
        return sum;
    }
};
